package com.gitee.feizns.explore.data_structure.union_find;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

/**
 * @author feizns
 * @since 2020/3/13
 */
public class TrulyMostPopular {

    public static void main(String[] args) {
        trulyMostPopular(new String[]{ "John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)" }, new String[]{
                "(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"
        });
    }

    public static String[] trulyMostPopular(String[] names, String[] synonyms) {
        Map<String, Integer> map = resolveNames(names);
        Uf uf = new Uf();
        for (String synonym : synonyms) {
            String[] pair = resolve(synonym);
            uf.union(pair[0], pair[1]);
        }
        Map<String, Integer> ret = new HashMap<>();
        for (String root : uf.ROOTS)
            ret.put(root, 0);
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            String r = uf.find(entry.getKey());
            ret.put(r, ret.getOrDefault(r, 0) + entry.getValue());
        }
        return mapToName(ret);
    }

    private static String[] mapToName(Map<String, Integer> map) {
        String[] ret = new String[map.size()];
        int index = 0;
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            ret[index++] = entry.getKey() + "(" + entry.getValue() + ")";
        }
        return ret;
    }

    private static String[] resolve(String syn) {
        int sp = syn.indexOf(",");
        return new String[]{ syn.substring(1, sp), syn.substring(sp + 1, syn.length() - 1) };
    }

    private static Map<String, Integer> resolveNames(String[] names) {
        Map<String, Integer> ret = new HashMap<>();
        for (String name : names) {
            int i = name.lastIndexOf("(");
            String n = name.substring(0, i);
            String v = name.substring(i + 1, name.length() - 1);
            ret.put(n, Integer.valueOf(v));
        }
        return ret;
    }

    static class Uf {
        Map<String, String> PARENTS = new HashMap<>();
        Set<String> ROOTS = new HashSet<>();
        void add(String q) {
            if ( !PARENTS.containsKey(q) ) {
                PARENTS.put(q, q);
                ROOTS.add(q);
            }
        }
        void union(String q, String p) {
            add(q);
            add(p);
            String qr = find(q);
            String pr = find(p);
            if ( !qr.equals(pr) ) {
                if ( qr.compareTo(pr) < 0 ) {
                    PARENTS.put(pr, qr);
                    ROOTS.remove(pr);
                } else {
                    PARENTS.put(qr, pr);
                    ROOTS.remove(qr);
                }
            }
        }
        String find(String q) {
            add(q);
            String s = PARENTS.get(q);
            if ( !s.equals(q) )
                PARENTS.put(q, find(s));
            return PARENTS.get(q);
        }
    }

}
